package com.origin.niuke.graph;

import java.util.Arrays;
import java.util.Comparator;

/**
 * NC159 最小生成树
 * 算法：kruskal + 并查集
 * 将边按照花费从小到大排序
 * parent[i] 表示 i 的父节点, 父节点都相同, 表示这些节点已经连通了
 *
 * @author yezh
 * @date 2022/11/19 22:15
 */
public class NC159 {

    public int miniSpanningTree (int n, int m, int[][] cost) {
        // write code here
        Arrays.sort(cost, Comparator.comparingInt(a -> a[2]));
        int [] parent = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
        int ans = 0;
        for (int[] verge : cost) {
            int px = find(parent, verge[0]);
            int py = find(parent, verge[1]);
            if (px != py) {
                parent[px] = py;
                ans += verge[2];
            }
        }
        return ans;
    }

    int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }

}
